package com.mgq.algorithm.array;

/**
 * 判断数组的大小
 *
 */
public class ArrayAlgorithm {

    public static void main(String[] args) {
        int[] array=new int[]{1,1,2,2,3,3,4,4,5,5,6,6,6,6,7,7,7,9,9,9,9,9};
        //demo1(array);
        demo2(array);
    }

    /**
     * 有一个int数组,里面有一种数出现了奇数次,其他出现了偶数次,O(n)求奇数次的数?
     * @param array
     */
    public static void demo1(int[] array) {
        int tmp=0;
        for (int i = 0; i < array.length; i++) {
            tmp = tmp ^ array[i];
        }
        System.out.println(tmp);
    }
    /**
     * 有一个int数组,里面有两种数出现了奇数次,其他出现了偶数次,O(n)求奇数次的这2个数?
     * @param array
     */
    public static void demo2(int[] array) {
        int tmp=0;
        for (int i = 0; i < array.length; i++) {
            tmp = tmp ^ array[i];
        }
        //此时tmp 是 a^b的值
        System.out.println(tmp);
        //tmp在某一位上肯定不是0 因为a!=b 且 a!=b!=0
        //那么 a或者b肯定某一位不一样(一样的话异或就为0了)
        //& 取反+1就得到某个数最右边第一个是1的位数
        int rightOne=tmp &(~tmp +1);
        int onlyOne=0;
        for (int i = 0; i < array.length; i++) {
            int cur = array[i];
            //对数组的每一个数和rightOne 进行与运算,==0或者==1,这时进行分组
            //得到的就是a或者b
            if ((cur & rightOne) == 0) {
                onlyOne = onlyOne ^ cur;
            }
        }
        //a^b^a=b
        //a^b^b=a
        //所以tmp
        int a=tmp^onlyOne;
        System.out.println("这2个数是:"+a+",另外一个数是:"+onlyOne);
    }
}
